Local Area Networks (LANs) connect computing systems together. LANs of all types can be connected together using Media Access Control (MAC) bridges, as set forth in the “IEEE Standard for Information Technology, Telecommunications and Information Exchange between Systems, Local and Metropolitan Area Networks, Common Specifications, Part 3: Media Access Control (MAC) Bridges,” published as ANSI/IEEE Standard 802.1D (1998), which is incorporated herein by reference. The 802.1D standard is available at standards.ieee.org/getieee802/download/802.1D-1998.pdf.
Each computing system connects to a LAN through a MAC device. MAC bridges that implement the 802.1D standard allow MAC devices attached to physically separated LANs to appear to each other as if they were attached to a single LAN. A MAC bridge functions within the Logical Link Control (LLC) sublayer of the Network Layer defined in ISO/IEC standard 7498-1:1994, entitled “Information Processing Systems-Open Systems Interconnection-Basic Reference Model-Part 1: The Basic Model” (available from the American National Standards Institute, New York, N.Y.), which is incorporated herein by reference. The bridge includes two or more MAC devices that interconnect the bridge ports to respective LANs.
MAC bridges maintain a database to map destination MAC addresses of the packets they receive to bridge ports. The bridge builds the database by means of a learning process, in which it associates the source MAC address of each incoming packet with the port on which the packet was received. When the bridge receives an incoming packet whose destination address is not located in the database, it broadcasts the packet through all its available ports, except the one through which the packet arrived. Other MAC bridges that do not recognize the destination address will further broadcast the packet. Through the broadcast mechanism, the packet will eventually traverse all interconnected bridges, and will ultimately reach its destination. A similar broadcast operation is performed independently for having a destination MAC address of a broadcast or multicast group, although the multicast scope may be reduced if the bridge is aware (by use of special protocols) of the physical locations of the target addresses in each multicast group. The operation of broadcast or multicast of a packet is referred to (independently of the reason) as a flooding process.
Multiprotocol Label Switching (MPLS) is gaining popularity as a method for efficient transportation of data packets over connectionless networks, such as Internet Protocol (IP) networks. MPLS is described in detail by Rosen et al., in Request for Comments (RFC) 3031 of the Internet Engineering Task Force (IETF), entitled “Multiprotocol Label Switching Architecture” (Jan., 2001), which is incorporated herein by reference. This RFC, as well as other IETF RFCs and drafts cited hereinbelow, is available at www.ietf.org. In conventional IP routing, each router along the path of a packet sent through the network analyzes the packet header and independently chooses the next hop for the packet by running a routing algorithm. In MPLS, however, each packet is assigned to a Forwarding Equivalence Class (FEC) when it enters the network, depending on its destination address. The packet receives a short, fixed-length label identifying the FEC to which it belongs. All packets in a given FEC are passed through the network over the same path by label-switching routers (LSRs). Unlike IP routers, LSRs simply use the packet label as an index to a look-up table, which specifies the next hop on the path for each FEC and the label that the LSR should attach to the packet for the next hop.
Since the flow of packets along a label-switched path (LSP) under MPLS is completely specified by the label applied at the ingress node of the path, a LSP can be treated as a tunnel through the network. Such tunnels are particularly useful in network traffic engineering, as well as communication security. MPLS tunnels are established by “binding” a particular label, assigned at the ingress node to the network, to a particular FEC.
One of the most promising uses of MPLS tunnels is in transporting layer-2 packets, such as Ethernet frames or ATM cells, over high-speed, high-performance packet networks. Methods for this purpose are described, for example, by Martini et al., in “Encapsulation Methods for Transport of Ethernet Frames Over IP/MPLS Networks” (IETF draft-ietf-ethernet-encap-00.txt, August, 2002), which is incorporated herein by reference. This draft defines mechanisms for encapsulating Ethernet traffic for transportation over IP networks using MPLS or other tunneling methods, such as Generic Routing Encapsulation (GRE), as are known in the art. L2TPv3, described by Townsley et al in “Layer Two Tunneling Protocol (Version 3) ‘L2TPv3’” (IETF draft-ietf-12tpext-12tp-base-04.txt, Nov., 2002), which is incorporated herein by reference, is another technique for tunneling layer-2 packets over IP networks, which can be used, inter alia, to carry Ethernet packets within a provider network. The term “layer 2” refers to the second layer in the protocol stack defined by the well-known Open Systems Interface (OSI) model, also known as the logical link, data link, or MAC, layer.
According to the model proposed by Martini et al., native Ethernet LANs are connected to the IP network by provider edge (PE) devices, which are linked one to another by tunnels through the IP network. The sending (ingress) PE device receives Ethernet frames from a customer edge (CE) device on the source LAN. It encapsulates the frames in packets with the label stack required for transmitting the packets through the appropriate tunnel to the receiving (egress) PE device.
The label structure includes a “PW demultiplexer” label (or virtual connection-VC label), which is used by the egress PE device to recognize the context of the packet if multiple connections share the same tunnel. Based on the PW demultiplexer label, the PE device de-encapsulates the frame and, optionally, adds a VLAN tag for transmission on the target LAN to the destination CE device. Details of the PW demultiplexer structure are described by Bryant et al. in an IETF draft entitled “Protocol Layering in PWE3” (IETF draft-ietf-pwe3-protocol-layer-00.txt, May, 2002), which is incorporated herein by reference. Martini et al. specify label distribution procedures for binding the VC label to the desired service in the case of MPLS transport in a further draft entitled “Transport of Layer 2 Frames over MPLS” (IETF draft-ietf-pwe3-control-protocol-01.txt, November, 2002), which is also incorporated herein by reference.
As a result of this encapsulation and associated processing functions, the IP network emulates Ethernet trunking behavior and can thus be treated as an Ethernet “pseudo wire” (PW). In other words, from the point of view of native Ethernet LANs that are connected to tunnels through the IP network, each PW is a virtual Ethernet point-to-point connection, emulating a physical connection between two Ethernet ports.
Taking this functionality a step further, Lasserre et al. describe a method to create a virtual private LAN service (VPLS) using a MPLS network in “Virtual Private LAN Services over MPLS” (IETF draft-lasserre-vkompella-ppvpn-vpls-02.txt, June, 2002), which is incorporated herein by reference. Although this reference is limited in scope to MPLS tunneling, the PW connection between the nodes can more generally be implemented using any available PW protocol, such as GRE or L2TPv3. A VPLS (also known as a transparent LAN service—TLS) provides bridge-like functionality between multiple sites over a large network. Users connect to the VPLS via regular node interfaces, and PWs between the nodes to which the users are connected form the VPLS entity itself. Every node in a VPLS acts as a virtual bridge. A virtual bridge node has “virtual ports,” which are the endpoints of PWs that are part of the VPLS. The interfaces to which the users are actually connected are physical ports at the network edges. Both virtual and real interfaces are treated identically from the point of view of frame forwarding and address learning. A single provider node can participate in multiple VPLS instances, each belonging to a different user.
The VPLS network topology is completely specified by the PW connections. When the PW connections are MPLS tunnels, the VPLS depends on the MPLS protocol to actually transfer the packets through the network. Since MPLS networks supply an alternative, virtual implementation of layer-2 network communications, VPLS can be thought of as parallel to conventional virtual bridged local area networks, as specified in the IEEE 802.1Q standard. From the perspective of the end-user, the VPLS network is transparent. The user is provided with the illusion that the provider network is a single LAN domain. User nodes on different physical LANs can thus be joined together through VPLS connections to define a virtual private network (VPN), which appears to the users to be a single Ethernet LAN.
VPLS networks are still in the development stage, and there are as yet no clear standards for loop prevention in such networks. One possible solution to avoiding loops in VPLS topologies is to configure the VPLS network as a full mesh of tunnels, as specified by Lasserre et al. in the above-mentioned draft. In a full mesh, each PE is directly connected to every other PE in the same VPN by a single PW. To avoid loops in the VPN, Lasserre et al. require that all PEs support a “split horizon” scheme, meaning that a PE must not forward traffic from one PW to another, although it may (and should) forward traffic from one physical port to another and between physical ports and the PWs. Considering the scope of flooding generally, a packet to be flooded coming from a PW will never be copied to another PW on the full mesh side, but is flooded to all Ethernet ports on the same VPN. An Ethernet packet to be flooded arriving from a physical port is copied to all other physical ports and to all the full mesh PWs of the same VPN. This split behavior differs from the traditional model of 802.1D bridges.
“Hierarchical VPLS” is an extension to the VPLS model, which is also described by Lasserre et al. in the above-mentioned draft. In hierarchical VPLS, some or all of the physical interfaces on one side of the split horizon can be replaced by point-to-point PWs, which act as logical extensions of physical ports of remote nodes. In this case, there are both full mesh PWs and point-to-point PWs (and possibly even physical ports) associated with the same VPN. Nodes with only point-to-point PWs are considered to be on the “access side” of the network, and are referred to as “edge nodes.” Nodes with full mesh PWs are considered to be in the “core side” of the network, and are referred to as “core nodes.” The scope of forwarding and flooding is the same as described above for full mesh PWs and physical ports.
In the Hierarchical VPLS model, protection against some failures is achieved by backup point-to-point PWs between each edge node and an additional core node (also referred to as “redundant” or “protection” PWs). This backup PW connection is in addition to the “standard” PW connection already existing between the edge node and another core node. Thus, if a VC between an edge node and a core node fails, a backup “protection path” through another core node can be used to provide access between the edge node and the rest of the network.
Hierarchical VPLS has the advantages of reducing significantly both the number of connections in the network and the number of times a packet needs to replicated in the learning process, when compared with a standard full mesh topology. The failure protection scheme suggested by Lasserre et al., however, can result in a long period of traffic outage if a virtual connection fails between an edge node and a core node, or if a core node fails. In most cases, initiation of failure protection depends on MAC address aging and learning schemes, which are inherently slow. Lasserre et al. in the above-mentioned draft make no provisions for handling multiple failures at once. In addition, the need to handle both standard connections (to edge nodes and other core nodes) and backup protection connections (to edge nodes) complicates the design of the VPLS core nodes and of the network as a whole.
An alternative hierarchical solution for VPLS connectivity is defined by Sodder et al. in an IETF draft entitled “Virtual Hierarchical LAN Services” (IETF draft-sodder-ppvpn-vhls-01.txt, November, 2002) which is incorporated herein by reference. While Sodder's PW encapsulation is different from the format defined in the above-mentioned references, the system topology (called VHLS in the Sodder draft) is very similar to that described above. MAC learning by edge nodes in Sodder's system is carried out hierarchically from the MAC point of view (MAC in MAC encapsulation). In terms of the operation of core devices and network topology, however, VHLS is substantially the same as the VPLS described by Lasserre et al.